package main

import (
	"fmt"
	"sync"
)

//链表形式的下压栈，后进先出
//链表栈 后进先出

type LinkStack struct {
	root *LinkNode  //链表起点
	size int        //栈中的元素
	lock sync.Mutex //并发安全 加锁
}

//栈节点

type LinkNode struct {
	Next  *LinkNode
	Value string
}

//入栈
// 将元素入栈，会先加锁实现并发安全，如果栈里面的底层链表为空，表明没有元素
// 那么新建节点并设置为链表的起点 stack.root=new(LinkNode)
//否则取出老的节点:preNode:=stack.root，新建节点:newNode:=new(LinkNode)
// 然后将原来老的节点链接在新的节点后面，最后将新节点设置为链表的起点

func (stack *LinkStack) Push(v string) {
	stack.lock.Lock()
	defer stack.lock.Unlock()

	//如果栈顶为空，那么增加节点
	if stack.root == nil {
		stack.root = new(LinkNode)
		stack.root.Value = v
	} else {
		//否则新元素插入链表的头部
		//原来的链表
		preNode := stack.root

		//新节点
		newNode := new(LinkNode)
		newNode.Value = v

		//原来的链表链接到新元素后面
		newNode.Next = preNode

		//将新节点放到头部
		stack.root = newNode
	}
	// 栈中元素数量+1
	stack.size = stack.size + 1
}

//出栈 这里元素出栈，如果栈的大小为0，那么将不允许出栈
// 直接将链表的第一个节点的值取出 然后将表头设置为链表的下一个节点

func (stack *LinkStack) Pop() string {
	stack.lock.Lock()
	defer stack.lock.Unlock()

	//栈中元素已空
	if stack.size == 0 {
		panic("empty")
	}

	//顶部元素出栈
	topNode := stack.root
	v := topNode.Value

	//将顶部元素后继链接上
	stack.root = topNode.Next

	//栈中元素数量-1
	stack.size = stack.size - 1

	return v
}

// 获取栈顶的元素

func (stack *LinkStack) Peek() string {
	//栈中元素已空
	if stack.size == 0 {
		panic("empty")
	}

	//顶部元素值
	v := stack.root.Value
	return v
}

//获取栈大小和判断是否为空

func (stack *LinkStack) Size() int {
	return stack.size
}

func (stack *LinkStack) IsEmpty() bool {
	return stack.size == 0
}

func main() {
	linkStack := new(LinkStack)
	linkStack.Push("hello")
	linkStack.Push("hi")
	linkStack.Push("haha")
	linkStack.Pop()
	fmt.Println(linkStack)
}
